#ifndef _OVERLAY_H_
#define _OVERLAY_H_

#include "util.h"
#include <map>

template <class K, class V> struct OverMap { 
  typedef map<K, V> M;
  M * base_;
  M * overlay_;
  V deleted_key_;

  OverMap(M * base, bool base_mode, V deleted_key) {
    base_ = base;
    overlay = NULL;
    if (!base_mode) overlay_ = new M;
    deleted_key_ = deleted_key;
  }

  struct iterator { 
    // iter_ points at one of the maps, based on base_
    OverMap *m_;
    M::iterator iter_;
    bool base_;
    iterator() {}
    iterator (OverMap *m, M::iterator iter, bool base) 
    :m_(m), iter_(iter), base_(base) {}
    bool AtEnd() { return (iter_ == m_->base_->end()); }
    pair<K, V> & operator *() { return *iter_; }
  };
  
  iterator end() {
    return iterator(this, base_.end(), true);
  }
  
  iterator find(const K & k) {
    if (overlay_) {
      M::iterator look = overlay_->find(k);
      if (look != overlay_->end()) {
	if (look->second == deleted_key_) return end();
	return iterator(this, look, false);
      }
    }
    M::iterator look_b = base_->find(k);
    return iterator(this, look, true);
  }

  iterator next(const iterator & iter) {
    if (!overlay_) {
      M::iterator i = iter.iter_; i++;
      return iterator(this, i, true);
    }
    K k = iter->first;
    if (iter.base_) {
      M::iterator next_overlay = overlay_->lower_bound(k);
      while (next_overlay != overlay_->end() && 
	     ((next_overlay->first == k) 
	      || next_overlay->second == deleted_value_)) next_overlay++;
      M::iterator next_base = iter.iter_;
      next_base++;
      while (next_base != base_->end() && 
	     IsDeleted(next_base->first)) next_base++;
    }
    
  }
};





#endif
